/*
 * prime.c
 *
 *  Created on: 2015年1月19日
 *      Author: chens
 */

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>
#define N 1000001

static char prime[N];

void method1()
{
	int i, j, num = 0;
	for (i = 2; i < N; i++) {
		for (j = 2; j <= sqrt(i); j++)
			if (i % j == 0)
				break;
		if (j > sqrt(i))
			prime[i] = 1;
	}
}


void method2()
{
	int i, j;
	prime[1] = 1;
	prime[2] = 1;
	for (i = 3; i < N; i++)
		if (i % 2 == 1)
			prime[i] = 1;
		else
			prime[i] = 0;//偶数

	for (i = 3; i <= sqrt(N) + 1; i++) {
		if (prime[i] == 1)
			for (j = i + i; j < N; j += i)
				prime[j] = 0;
	}
}

int main(int argc, char **argv)
{
	struct timeval begin, end;
	gettimeofday(&begin, NULL);
	if(argc >= 2)
		method2();
	else
		method1();

	gettimeofday(&end, NULL);
	unsigned time_other = (end.tv_sec - begin.tv_sec) * 1000000
			+ (end.tv_usec - begin.tv_usec);
	printf("Time: %d sec\n", time_other / 1000000);

	int i;
	for (i = N - 100; i > 0 && i < N; i++)
		if (prime[i] == 1)
			printf("%d ", i);


	return 0;
}

